/**
 * 爬楼梯问题
 *
 * @Author: wanqian
 * @Date: 2021/3/1 9:25
 */
public class ClimbStairsDemo {

    public static void main(String[] args) {
        System.out.println(climbStairs(5));

    }

    /**
     * 递归求解
     *
     * @param n 级台阶
     * @return 多少种跳法
     */
    public static int climbStairs(int n) {
        if (n < 0) {
            return -1;
        }

        if (n <= 2) {
            return n;
        }
        //可理解为如果最后一次跳一级的跳法 + 最后跳两级的跳法
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    /**
     * 动态规划求解
     *
     * @param n 级台阶
     * @return 多少种跳法
     */
    public static int climbStairsDynamic(int n) {
        if (n <= 0) return -1;
        if (n == 1) return 1;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static int climb(int n) {
        if (n < 0) {
            return -1;
        }
        if (n <= 2) {
            return n;
        }
        return climb(n - 1) + climbStairs(n - 1);
    }

    public static int climbDy(int n) {
        if (n < 0) {
            return -1;
        }
        if (n <= 2) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < dp.length; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
